//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：["()"]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
// Related Topics 字符串 动态规划 回溯 👍 2724 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

class 括号生成 {
    public static void main(String[] args) {
        Solution solution = new 括号生成().new Solution();
        List<String> list = solution.generateParenthesis(3);
        System.out.println(list);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> generateParenthesis(int n) {
            //n对括号 组成2n长度的括号对
            char[] path = new char[n << 1];
            List<String> ans = new ArrayList<>();
            process(path, 0, 0, n, ans);
            return ans;
        }


        // path 做的决定  path[0....index-1]做完决定的！
        // path[index.....] 还没做决定，当前轮到index位置做决定！
        public void process(char[] path, int index, int leftMinusRight, int leftRest, List<String> ans) {
            if (index == path.length) {
                ans.add(String.valueOf(path));
            }
            //排除没必要的分支  剪枝
            else{
                if (leftRest > 0) {
                    path[index] = '(';
                    process(path, index + 1, leftMinusRight + 1, leftRest - 1, ans);
                }
                if (leftMinusRight > 0) {
                    path[index] = ')';
                    process(path, index + 1, leftMinusRight - 1, leftRest, ans);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
